home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / qlib205.zip / QLIB.ZIP / SRC / QLIB / LZW.ASM < prev    next >
Assembly Source File  |  1997-01-20  |  7KB  |  371 lines
  1. ;LZW compression v1.00
  2.  
  3. ; by : Peter Quiring
  4.  
  5. ; NOTE : This is a unique twist to LZW.  This will not work on LZW or LHA
  6. ; files. (in fact I have no idea exactly what the LZW compress is in them)
  7.  
  8. ;256 = clear code
  9. ;257 = EOF
  10. ;258 = first avail. code
  11.  
  12. include qlib.inc
  13. include lzw.inc
  14.  
  15. CLR_CODE equ 256
  16. EOF_CODE equ 257
  17. FIRST_CODE equ 258
  18.  
  19. ; global data for (de)compressor
  20. ; for a good explaination of how to use this see "lzw.txt"
  21. ; for a good explaination of how LZW compression works see my tutorials
  22. ;   on my homepage
  23.  
  24. .data?
  25.   ;dwords
  26.   public lzw_ht   ;in case you wanna dump it
  27.   lzw_ht label byte
  28.   ht dd 4096 dup (?)     ;hash table (16k-ouch!) (dwords for faster comparison)
  29.     ;format : [empty db][suffix db][prefix dw]
  30.   ;words
  31.   code dd ?              ;current code
  32.   s dw ?                 ;string (prefix code)
  33.   nb db ?                ;number of bits to output
  34.   ;bytes
  35.   bo db ?                ;bit offset of output/input
  36.   b db ?                 ;byte   (suffix code)
  37.   oc dw ?                ;old code
  38.   nc dw ?                ;new code
  39.   bad_lzw db ?           ;==1 if the LZW compressed data if faulty
  40.   dlen dd ?              ;used in decompression
  41.   tlen dd ?              ;total length of data
  42.  
  43. .code
  44. coutput proc private,d:word
  45.   mov ax,d
  46.   mov cl,16
  47.   sub cl,nb
  48.   shl ax,cl
  49.  
  50.   mov cl,bo  ;shift
  51.   mov ch,nb  ;counter
  52. @@:
  53.   rcl ax,1
  54.   .if carry?
  55.     mov dl,1
  56.     shl dl,cl
  57.     or [edi],dl
  58.   .endif
  59.   dec cl
  60.   .if cl==255
  61.     inc edi
  62.     mov [edi],bptr 0
  63.     mov cl,7
  64.   .endif
  65.   dec ch
  66.   jnz @b
  67.   mov bo,cl
  68.   ret
  69. coutput endp
  70.  
  71. getbyte macro
  72.   xor eax,eax
  73.   lodsb
  74.   dec len
  75. endm
  76.  
  77. lzw_compress proc,dest:dword,src:dword,len:dword
  78.   pushad
  79.   mov edi,dest
  80.   mov esi,src
  81.   mov eax,len
  82.   stosd
  83.   mov dptr[edi],0
  84.   mov bo,7            ;current bit offset
  85. restart:
  86.   mov nb,9            ;# bits (9)
  87.   mov code,FIRST_CODE ;1st avail code
  88.   .if !len
  89.     jmp codone
  90.   .endif
  91.   getbyte
  92.   mov s,ax
  93.   .if !len
  94.     callp coutput,ax
  95.     jmp codone
  96.   .endif
  97.   callp coutput,ax
  98.   getbyte
  99.   mov b,al
  100.   .if !len
  101.     callp coutput,ax
  102.     jmp codone
  103.   .endif
  104.   xor eax,eax
  105.   mov ah,b
  106.   shl eax,8
  107.   mov ax,s
  108.   mov dptr[ht],eax
  109.   inc code  ;move to next avail code
  110. do1: ;repeat until code > 12 bits & restart here for larger repeat
  111.     xor ah,ah
  112.     mov al,b
  113.     mov s,ax   ;s=b
  114.     getbyte
  115.     mov b,al
  116.     .if !len
  117.       callp coutput,s
  118.       callp coutput,b
  119.       jmp codone
  120.     .endif
  121. do2: ;repeat until we find a new string
  122.     mov ecx,code
  123.     mov edx,ecx
  124.     sub ecx,FIRST_CODE  ;ecx=# of entries in hash table
  125.     push edi
  126.     mov edi,offset ht
  127.     xor eax,eax
  128.     mov ah,b
  129.     shl eax,8
  130.     mov ax,s
  131.     repnz scasd
  132.     pop edi
  133.     jnz c1
  134.   ;not a new string (keep looking)
  135.     inc cx             ;move back to code that was the same
  136.     sub dx,cx
  137.     mov s,dx
  138.     getbyte
  139.     mov b,al
  140.     .if !len
  141.       callp coutput,s 
  142.       callp coutput,b
  143.       jmp codone
  144.     .endif
  145.     jmp do2
  146. c1:  
  147.     ;got a new string
  148.     ;place s,b into hash table  
  149.     mov ebx,code
  150.     sub ebx,FIRST_CODE
  151.     xor eax,eax
  152.     mov ah,b
  153.     shl eax,8
  154.     mov ax,s
  155.     shl ebx,2 ;*4
  156.     mov [ebx+ht],eax
  157.     callp coutput,s
  158.     inc code
  159.     cmp code,200h   ;10bit
  160.     jnz @f
  161.     inc nb
  162.     jmp do1
  163. @@:
  164.     cmp code,400h   ;11bit
  165.     jnz @f
  166.     inc nb
  167.     jmp do1
  168. @@:
  169.     cmp code,800h   ;12bit
  170.     jnz @f
  171.     inc nb
  172.     jmp do1
  173. @@:
  174.     cmp code,1000h  ;13bit = restart
  175.     jnz do1
  176.   ; end of this block  (send reset code and restart hash table)
  177.     callp coutput,b
  178.     callp coutput,CLR_CODE
  179.     jmp restart
  180. codone:  ;done!
  181.   callp coutput,EOF_CODE
  182.   .if bo!=7
  183.     inc edi ;to get last part
  184.   .endif
  185.   sub edi,dest
  186.   mov [esp+4*7],edi  ;save EAX for ret val (size of compressed data)
  187.   popad
  188.   ret
  189. lzw_compress endp
  190.  
  191. getcode proc private
  192.   xor eax,eax
  193.   mov bl,[esi]
  194.   mov cl,7
  195.   sub cl,bo
  196.   shl bl,cl
  197.   mov cl,bo
  198.   mov ch,nb
  199. @@:
  200.   rcl bl,1
  201.   rcl ax,1
  202.   dec cl
  203.   .if cl==255
  204.     inc esi
  205.     mov bl,[esi]
  206.     mov cl,7
  207.   .endif
  208.   dec ch
  209.   jnz @b
  210.   mov bo,cl
  211.   ret
  212. getcode endp
  213.  
  214. doutput proc private   ;output string and return 1st byte
  215.   ;output the whole string and return the 1st byte of string
  216.   ;put 1st byte into hash table (so that last byte of string will
  217.   ;  be successfully outputed (it's very confusing)
  218.  
  219.   ;nc=code obtained from input stream data
  220.   ;code=current code pos in hash table
  221.  
  222.   local flg:byte,fb:byte
  223.  
  224.   mov flg,0  ;indicates that string used does not have a suffix
  225.   mov ebx,esp  ;save stack pos
  226.   xor eax,eax
  227.   mov ax,nc    ;to be outputed
  228. @@:
  229.   .if ax<100h
  230.     ;push code and done!
  231.     mov fb,al    ;first byte
  232.     dec esp
  233.     mov [esp],al
  234.     jmp done
  235.   .endif
  236.   .if eax==code
  237.     mov ax,oc  ;then it simply is the OC
  238.     .if flg
  239.       jmp bad
  240.     .endif
  241.     inc flg  ;this can only happen once (if it happens more the data is corrupt)
  242.     jmp @b
  243.   .endif
  244. ;push the suffix
  245.   xor ecx,ecx
  246.   mov cx,ax
  247.   sub cx,FIRST_CODE
  248.   shl ecx,2
  249.   add ecx,offset ht
  250.   mov al,[ecx+2]      ;get suffix
  251.   dec esp
  252.   mov [esp],al
  253.   mov ax,[ecx]    ;get prefix
  254.   jmp @b
  255. done:
  256.   ;undo stack
  257. @@:
  258.   mov al,[esp]
  259.   stosb
  260.   inc esp
  261.   inc dlen
  262.   dec tlen
  263.   .if esp!=ebx
  264.     .if !tlen
  265.       jmp bad
  266.     .endif
  267.     jmp @b
  268.   .endif
  269.   mov al,fb
  270.   .if flg
  271.     ;output fb again
  272.     stosb
  273.     inc dlen
  274.     .if !tlen
  275.       jmp bad
  276.     .endif
  277.     dec tlen
  278.   .endif
  279.   ret
  280. bad:
  281.   inc bad_lzw
  282.   ret
  283. doutput endp
  284.  
  285. lzw_decompress proc,dest:dword,src:dword
  286.   
  287.   pushad
  288.   mov bo,7
  289.   mov nb,9
  290.   mov esi,src
  291.   mov edi,dest
  292.   lodsd
  293.   mov tlen,eax
  294.   mov dlen,0
  295.   mov bad_lzw,0
  296. restart:
  297.   mov nb,9
  298.   mov code,FIRST_CODE
  299.   call getcode
  300.   mov oc,ax
  301.   .if ax==EOF_CODE
  302.     jmp dedone
  303.   .endif
  304.   .if !tlen
  305.     jmp bad
  306.   .endif
  307.   .if ax>=100h
  308.     jmp bad
  309.   .endif
  310.   stosb
  311.   inc dlen
  312. dc1:  ;repeat until we get code EOF CODE
  313.     .if bad_lzw
  314.       jmp bad
  315.     .endif
  316.     call getcode
  317.     .if ax==EOF_CODE
  318.       jmp dedone
  319.     .endif
  320.     .if !tlen
  321.       jmp bad
  322.     .endif
  323.     .if ax==CLR_CODE
  324.       jmp restart
  325.     .endif
  326.     mov nc,ax
  327.     call doutput
  328.     mov b,al
  329.     mov ebx,code
  330.     sub ebx,FIRST_CODE
  331.     shl ebx,2
  332.     xor eax,eax
  333.     mov ah,b
  334.     shl eax,8
  335.     mov ax,oc
  336.     mov [ebx+ht],eax
  337.     inc code
  338.     .if code==512 || code==1024 || code==2048
  339.       inc nb
  340.     .elseif code==4096
  341.       call getcode  ;must be clear code now
  342.       .if ax==CLR_CODE
  343.         jmp restart
  344.       .else
  345.         ;may be last code
  346.         .if ax<100h
  347.           stosb
  348.           call getcode
  349.           .if ax==CLR_CODE
  350.             jmp restart
  351.           .endif
  352.         .endif
  353.       .endif
  354.       jmp bad
  355.     .endif
  356.     mov ax,nc       ;oc=nc;
  357.     mov oc,ax
  358.     jmp dc1
  359. dedone:
  360.   popad
  361.   mov eax,dlen
  362.   ret
  363. bad:
  364.   popad
  365.   mov eax,ERROR
  366.   ret
  367. lzw_decompress endp
  368.  
  369. end
  370.  
  371.